namespace HashNoNormal
{
	enum State { EMPTY, EXIST, DELETE };

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state;

		// 可写可不写，（默认构造）pair有自己的默认构造，_state
		HashData(const pair<K, V>& kv = pair<K, V>())
			:_kv(kv)
		{
			_state = EMPTY;
		}
	};

	template<class K> struct HashKey
	{
		size_t operator()(const K& k)
		{
			return (size_t)k;
		}
	};
	template<> struct HashKey<string>
	{
		size_t operator()(const string& s)
		{
			size_t val = 0;
			for (size_t i = 0; i < s.size(); i++)
			{
				val *= 131;
				val += s[i];
			}
			return val;
		}
	};

	template<class K, class V, class Hash = HashKey<K>> class _HashTable
	{
	public:
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			if (_tables.size() == 0 || 10 * _size / _tables.size() == 7)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				_HashTable newHT;
				newHT._tables.resize(newSize);

				for (auto e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}

				_tables.swap(newHT._tables);
			}

			Hash hash;
			size_t hashi = hash(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			_size++;

			return true;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state == DELETE;
				_size--;
				return true;
			}
			
			return false;
		}

		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			Hash hash;
			size_t start = hash(key) % _tables.size();
			size_t hashi = start;

			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				hashi++;
				hashi %= _tables.size();

				if (start == hashi)
					break;
			}

			return nullptr;
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._state == EXIST)
				{
					cout << _tables[i]._kv.first << ':' << i << endl;
				}
			}
		}

		void PrintPair()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._state == EXIST)
				{
					cout << _tables[i]._kv.first << ':' << _tables[i]._kv.second << ':' << i << endl;
				}
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _size = 0;
	};
}

